package q113_pathSum;

import CommonClass.Common.TreeNode;

import java.util.ArrayList;
import java.util.List;

public class Solution {
    private List<List<Integer>> res = new ArrayList<>();
    private List<Integer> path = new ArrayList<>();
    public List<List<Integer>> pathSum(TreeNode root, int targetSum) {
        if (root == null) {
            return res;
        }
        path.add(root.val);
        dfs(root, targetSum - root.val, path);
        return res;
    }

    /*
    此题的递归思路和112几乎一致，只需要了解上一题即可
     */
    private void dfs(TreeNode root, int count, List path) {
        if (root.left == null && root.right == null && count == 0) {
            res.add(new ArrayList<>(path));
            return;
        }

//        if (root.left == null && root.right == null) {
//            return;
//        }

        if (root.left != null) {
            path.add(root.left.val);
            dfs(root.left, count - root.left.val, path);
            path.remove(path.size() - 1);
        }

        if (root.right != null) {
            path.add(root.right.val);
            dfs(root.right, count - root.right.val, path);
            path.remove(path.size() - 1);
        }
    }
}
